#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
int n,m,a[N],f[N],mx[N],ok[N];
pair<int,int> p[N];
inline int ask(int l,int r)
{
	int res = 2e18;
	for(int i = l;i<=r;i++)
		res = min(res,f[i]);
	return res;
}
inline bool cmp(pair<int,int> x,pair<int,int> y)
{
	if(x.first==y.first) return x.second>y.second;
	else return x.first<y.first;
}
signed main()
{
//	freopen("gonna.in","r",stdin);
//	freopen("gonna.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>a[i],ok[i] = 2e9;
	cin>>m;
	for(int i = 1,l,r;i<=m;i++)
		cin>>l>>r,p[i] = {l,r};
	sort(p+1,p+m+1,cmp);
	int mn = m;
	mx[p[mn].second] = max(mx[p[mn].second],p[mn].first);
//	cout<<"ok"<<p[mn].first<<' '<<p[mn].second<<'\n';
	for(int j = p[mn].first;j<=p[mn].second;j++)
		ok[j] = min(ok[j],p[mn].first);
	for(int i = m-1;i;i--)
	{
		if(p[i].second>=p[mn].second&&p[i].first<=p[mn].first) continue;
		mn = i;
		mx[p[i].second] = p[i].first;
		for(int j = p[i].first;j<=p[i].second;j++)
			ok[j] = min(ok[j],p[i].first);
//		cout<<"ok"<<p[i].first<<' '<<p[i].second<<'\n';
	}
	int now = 0,ans = 0;
	for(int i = 1;i<=n;i++)
	{
		f[i] = a[i];
//		cout<<i<<":"<<now<<' ';
		if(mx[i]>now) ans+=ask(mx[now],now);
		else if(now&&ok[i]<=now) f[i] = ask(mx[now],now)+a[i];
		if(mx[i]) now = i;
		cout<<f[i]<<" \n"[i==n];
//		cout<<mx[i]<<' '<<f[i]<<"\n";
	}
//	cout<<ans<<'\n';
	cout<<ans+ask(mx[now],now);
	return 0;
}
/*
5
61 20 70 57 46 5
5 5
2 4
2 3
4 5
3 3

5
23 35 86 12 11 5
3 5
1 1
1 5
2 3
1 3

5
35 74 92 39 99 5
2 2
1 3
4 5
1 4
3 5
*/
